package _17_剑指Offer;

public class _19_剑指Offer正则表达式匹配 {

    public static void main(String[] args) {

        _19_剑指Offer正则表达式匹配 v = new _19_剑指Offer正则表达式匹配();

        String str1 = "aaa";
        String str2 = "ab*a*c*a";
        System.out.println(v.isMatch(str1, str2));

    }

    public boolean isMatch(String s, String p) {
        char[] sChars = s.toCharArray();
        char[] pChars = p.toCharArray();
        int sLen = sChars.length;
        int pLen = pChars.length;
        boolean[][] dp = new boolean[sLen + 1][pLen + 1];
        // 初始化dp数据
        dp[0][0] = true;
        for (int i = 0; i <= sLen; i++) {
            for (int j = 1; j <= pLen; j++) {
                if (pChars[j - 1] == '*') {
                    if (match(sChars, i - 1, pChars, i - 2)) {
                        dp[i][j] = dp[i - 1][j] || dp[i][j - 2];
                    } else {
                        dp[i][j] = dp[i][j - 2];
                    }
                } else {
                    dp[i][j] = match(sChars, i - 1, pChars, i - 1) && dp[i - 1][j - 1];
                }
            }
        }
        return dp[sLen][pLen];
    }

    private boolean match(char[] sChars, int index1, char[] pChars, int index2) {
        if (index1 < 0) return false;

        if (pChars[index2] == '.') return true;

        return sChars[index1] == pChars[index2];
    }


}
